219. 存在重复元素 II

Similar Question

leading to the advanced question

Solution Tips

方案一: 哈希表

第一个遇到的, 索引肯定是最小的, 之后索引会越来越大, 但是万一有多个重复的元素呢? 那样索引是需要刷新的, 那样哈希表得存一个数组了, 因为会冲突, 需要遍历数组

但是其实只需要保留最新遇到的索引就好了, 因为索引越来越大, 旧的小索引不可能再符合要求了

var containsNearbyDuplicate = function(nums, k) {
    const map = new Map();
    const length = nums.length;
    for (let i = 0; i < length; i++) {
        const num = nums[i];
        if (map.has(num) && i - map.get(num) <= k) {
            return true;
        }
        map.set(num, i);
    }
    return false;
};

方法二: 滑动窗口

直接维护一个 k 大小的窗口就行, 同时用哈希表记录窗口内的字符数量, 如果有大于 2 的就返回 true

var containsNearbyDuplicate = function(nums, k) {
    const set = new Set();
    const length = nums.length;
    for (let i = 0; i < length; i++) {
        if (i > k) {
            set.delete(nums[i - k - 1]);
        }
        if (set.has(nums[i])) {
            return true;
        }
        set.add(nums[i])
    }
    return false;
};